Two key attributes of a premium paper towel are softness and a pleasing cloth-like visual texture. Softness can be enhanced by embossing the towel basesheet with a regular pattern of relatively small, discrete embossing elements, such as a pattern of dots. However, while the softness improvement is desirable, consumers tend to associate products having such regular embossing patterns with products of lower quality. It would be desirable to be able to soften a paper towel, for example, with an embossing pattern that is less objectionable to the consumer and promotes a cloth-like appearance.